package bytes

// Element is an element of a linked queue.
type Element struct {
	// Next and previous pointers in the doubly-linked queue of elements.
	// To simplify the implementation, internally a queue q is implemented
	// as a ring, such that &q.root is both the next element of the last
	// queue element (q.Back()) and the previous element of the first queue
	// element (q.Front()).
	next, prev *Element

	// The queue to which this element belongs.
	queue *BytesQueue

	// The value stored with this element.
	Value []byte
}

// Next returns the next queue element or nil.
func (e *Element) Next() *Element {
	if p := e.next; e.queue != nil && p != &e.queue.root {
		return p
	}
	return nil
}

// Prev returns the previous queue element or nil.
func (e *Element) Prev() *Element {
	if p := e.prev; e.queue != nil && p != &e.queue.root {
		return p
	}
	return nil
}

// NOT THREAD SAFE
// BytesQueue represents a doubly linked queue.
// The zero value for BytesQueue is an empty queue ready to use.
type BytesQueue struct {
	root Element // sentinel queue element, only &root, root.prev, and root.next are used
	len  int     // current queue length excluding (this) sentinel element
}

// Init initializes or clears queue q.
func (q *BytesQueue) Init() *BytesQueue {
	q.root.next = &q.root
	q.root.prev = &q.root
	q.len = 0
	return q
}

// New returns an initialized queue.
func NewBytesQueue() *BytesQueue { return new(BytesQueue).Init() }

// Len returns the number of elements of queue q.
// The complexity is O(1).
func (q *BytesQueue) Len() int { return q.len }

// Front returns the first element of queue q or nil.
func (q *BytesQueue) Front() *Element {
	if q.len == 0 {
		return nil
	}
	return q.root.next
}

// Back returns the last element of queue q or nil.
func (q *BytesQueue) Back() *Element {
	if q.len == 0 {
		return nil
	}
	return q.root.prev
}

// insert inserts e after at, increments q.len, and returns e.
func (q *BytesQueue) insert(e, at *Element) *Element {
	n := at.next
	at.next = e
	e.prev = at
	e.next = n
	n.prev = e
	e.queue = q
	q.len++
	return e
}

// remove removes e from its queue, decrements q.len, and returns e.
func (q *BytesQueue) remove(e *Element) *Element {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.queue = nil
	q.len--
	return e
}

// Remove removes e from q if e is an element of queue q.
// It returns the element value e.Value.
func (q *BytesQueue) Remove(e *Element) *Element {
	if e.queue == q {
		// if e.queue == q, q must have been initialized when e was inserted
		// in q or q == nil (e is a zero Element) and q.remove will crash
		q.remove(e)
	}
	return e
}

// PushFront inserts a new element e with value v at the front of queue q and returns e.
func (q *BytesQueue) PushFront(e *Element) {
	q.insert(e, &q.root)
}

// PushBack inserts a new element e with value v at the back of queue q and returns e.
func (q *BytesQueue) PushBack(e *Element) {
	q.insert(e, q.root.prev)
}

func (q *BytesQueue) InsertAfter(e, at *Element) {
	q.insert(e, at)
}
